CAST-128 is a block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has been approved for Canadian government use by the Communications Security Establishment. Haruki Seki et al. found 2-round differential characteristics and they can attack 5-round CAST-128. In this paper, we studied the properties of round functions F1 and F3 in CAST-128, and identified differential characteristics for F1 round function and F3 round function. So we identified a 6-round differential characteristic with probability 2-53 under 2-23.8 of the total key space. Then based on 6-round differential characteristic, we can attack 8-round CAST-128 with key sizes greater than or equal to 72 bits and 9-round CAST-128 with key sizes greater than or equal to 104 bits. We give the summary of attacks on reduced-round CAST-128 in Table 10.

MISTY1 is a 64-bit block cipher that has provable security against differential and linear cryptanalysis. MISTY1 is one of the algorithms selected in the European NESSIE project, and it has been recommended for Japanese e-Government ciphers by the CRYPTREC project. This paper shows that higher order differential attacks can be successful against 7-round versions of MISTY1 with FL functions. The attack on 7-round MISTY1 can recover a partial subkey with a data complexity of 254.1 and a computational complexity of 2120.8, which signifies the first successful attack on 7-round MISTY1 with no limitation such as a weak key. This paper also evaluates the complexity of this higher order differential attack on MISTY1 in which the key schedule is replaced by a pseudorandom function. It is shown that resistance to the higher order differential attack is not substantially improved even in 7-round MISTY1 in which the key schedule is replaced by a pseudorandom function.

This paper proposes a compact hardware (H/W) implementation for the MISTY1 block cipher, which is one of the ISO/IEC 18033-3 standard encryption algorithms. In designing the compact H/W, we focused on optimizing the implementation of FO/FI/FL functions, which are the main components of MISTY1. For this optimization, we propose three new methods; reducing temporary registers for the FO function, shortening the critical path for the FI function, and merging the FL/FL-1 functions. According to our logic synthesis on a 0.18-µm CMOS standard cell library based on our proposed methods, the gate size is 3.4 Kgates, which is the smallest as far as we know.

This article discusses the provable security of pseudo-random-function (PRF) modes of an iterated hash function using a block cipher. The iterated hash function uses the Matyas-Meyer-Oseas (MMO) mode for the compression function and the Merkle-Damgård with a permutation (MDP) for the domain extension transform. It is shown that the keyed-via-IV mode and the key-prefix mode of the iterated hash function are pseudorandom functions if the underlying block cipher is a pseudorandom permutation under a related-key attack with respect to the permutation used in MDP. More precisely, the key-prefix mode also requires that EIV(K)+ K is pseudoramdom, where E is the underlying block cipher, IV is the fixed initial value of the hash function, and K is a secret key. It is also confirmed that the MMO compression function is the best choice with MDP among the block-cipher-based compression functions in the Preneel-Govaerts-Vandewalle model in terms of the provable security.

Linear cryptanalysis using sieve methods is a technique proposed by Takeda et al. in 1998 as an attack capable of breaking ciphers with smaller amounts of data than linear cryptanalysis (LC) by using data that satisfies linear sieve conditions. This paper shows that when considering the amount of data required for cryptanalysis in Takeda et al.'s proposed sieved linear cryptanalysis (S-LC), it is necessary to take into account the independence of keys relating to the linear mask (Linear key) and keys relating to the linear sieve mask (Sieve key) in rounds that are affected by these keys. If p is the probability that the linear approximate expression holds and p* is the probability after applying the linear sieve, then it has been shown that when the Linear keys are independent of the Sieve keys, then it is necessary to select the linear mask and linear sieve mask so that a larger value of p*-p is obtained. It is also shown that the amount of data needed for S-LC cannot be reduced below the amount of data needed for LC when the Linear key and Sieve key are not independent. In fixed sieve linear cryptanalysis, it is shown that the amount of data needed for cryptanalysis cannot be reduced regardless of the independence of the Linear key and Sieve key.

This paper describes an extension of XEX* mode, which is a method to convert a block cipher into a tagged tweakable block cipher, a notion introduced by Rogaway in 2004 as an extension of the tweakable block cipher by Liskov et al. Our extension attaches an additional encryption function to the original XEX*, which has some limitation but is slightly faster than the encryption implemented by XEX*. We prove our scheme's security in a general form, where the offset function, a key component of our construction, is not restricted to the one used by XEX*. We also provide some applications of our result, in particular to OCB 2.0, an authenticated encryption based on XEX*.

MISTY1 is a 64-bit block cipher that has provable security against differential and linear cryptanalysis. MISTY1 is one of the algorithms selected in the European NESSIE project, and it has been recommended for Japanese e-Government ciphers by the CRYPTREC project. This paper reports a previously unknown higher order differential characteristic of 4-round MISTY1 with the FL functions. It also shows that a higher order differential attack that utilizes this newly discovered characteristic is successful against 6-round MISTY1 with the FL functions. This attack can recover a partial subkey with a data complexity of 253.7 and a computational complexity of 264.4, which is better than any previous cryptanalysis of MISTY1.

SHACAL-2 is a 64-round block cipher with a 256-bit block size and a variable length key of up to 512 bits. It is a NESSIE selected block cipher algorithm. In this paper, we observe that, when checking whether a candidate quartet is useful in a (related-key) rectangle attack, we can check the two pairs from the quartet one after the other, instead of checking them simultaneously; if the first pair does not meet the expected conditions, we can discard the quartet immediately. We next exploit a 35-round related-key rectangle distinguisher with probability 2-460 for the first 35 rounds of SHACAL-2, which is built on an existing 24-round related-key differential and a new 10-round differential. Finally, taking advantage of the above observation, we use the distinguisher to mount a related-key rectangle attack on the first 44 rounds of SHACAL-2 . The attack requires 2233 related-key chosen plaintexts, and has a time complexity of 2497.2 computations. This is better than any previously published cryptanalytic results on SHACAL-2 in terms of the numbers of attacked rounds.

In 1997, M. Matsui proposed secret-key cryptosystems called MISTY 1 and MISTY 2, which are 8- and 12-round block ciphers with a 64-bit block, and a 128-bit key. They are designed based on the principle of provable security against differential and linear cryptanalysis. In this paper we present large collections of weak-key classes encompassing 273 and 270 weak keys for 7-round MISTY 1 and 2 for which they are vulnerable to a related-key amplified boomerang attack. Under our weak-key assumptions, the related-key amplified boomerang attack can be applied to 7-round MISTY 1 and 2 with 254, 256 chosen plaintexts and 255.3 7-round MISTY 1 encryptions, 265 7-round MISTY 2 encryptions, respectively.

This paper presents MACs that combine a block cipher and its component such as a reduced-round version. Our MACs are faster than the standard MAC modes such as CBC-MAC, and provably secure if the block cipher is pseudorandom and its component is a permutation with a small differential probability. Such a MAC scheme was recently proposed by one of authors, and we provide improvements about security and treading-off between speed and amount of preprocessing.

The security notion of indifferentiability was proposed by Maurer, Renner, and Holenstein in 2004. In 2005, Coron, Dodis, Malinaud, and Puniya discussed the indifferentiability of hash functions. They have shown that the Merkle-Damgård construction is not secure in the sense of indifferentiability. In this paper, we analyze the security of single-block-length and rate-1 compression functions in the sense of indifferentiability. We formally show that all single-block-length and rate-1 compression functions, which include the Davies-Meyer compression function, are insecure. Furthermore, we show how to construct a secure single-block-length and rate-1 compression function in the sense of indifferentiability. This does not contradict our result above.

Knudsen and Meier applied the χ2-attack to RC6. The χ2-attack recovers a key by using high correlations measured by χ2-value. Up to the present, the success probability of any χ2-attack has not been evaluated theoretically without using experimental results. In this paper, we discuss the success probability of χ2-attack and give the theorem that evaluates the success probability without using any experimental result, for the first time. We make sure the accuracy of our theorem by demonstrating it on both 4-round RC6 without post-whitening and 4-round RC6-8. We also evaluate the security of RC6 theoretically and show that a variant of the χ2-attack is faster than an exhaustive key search for the 192-bit-key and 256-bit-key RC6 with up to 16 rounds. As a result, we succeed in answering such an open question that a variant of the χ2-attack can be used to attack RC6 with 16 or more rounds.

One of Kaliski and Robshaw's algorithms, which is used for the linear attack on block ciphers with multiple linear approximations and introduced as Algorithm 2M in this paper, looks efficient but lacks any theoretical and mathematical description. It means there exists no way to estimate the data complexity required for the attack by the algorithm except experiments of the reduced variants. In this paper we propose a new algorithm using multiple linear approximation. We achieve the theoretical and mathematical analysis of its success probability. The new algorithm needs about 240.6 plaintexts to find 12 bits of secret key of 16-round DES with a success probability of about 86%.

In the key recovery variant of the interpolation attack, exhaustive search is required to find the last round key Km. Therefore, this attack is almost impractical if the size of Km is too large. In this paper, we show that Km can be very efficiently obtained if F(K,x) can be approximated by a low degree polynomial gx(K) in K for any fixed x, where F is a round function of Feistel type block ciphers.

In [1] it was proved that 20 of 64 PGV hash functions based on block cipher are collision-resistant and one-way in the black-box model of the underlying block cipher. Here, we generalize the definition of PGV-hash function into a hash family and we will prove that, aside from the previously reported 20 hash functions, we have 22 more collision-resistant and one-way hash families. As all these 42 families are keyed hash family, these are also target-collision-resistant. All these 42 hash families have tight upper and lower bounds on (target) collision-resistant and one-way-ness.

KASUMI is a block cipher which has been adopted as a standard of 3GPP. In this paper, we study the pseudorandomness of idealized KASUMI type permutations for adaptive adversaries. We show that ●the four-round version is pseudorandom and ●the six-round version is super-pseudorandom.

f 8 and f 9 are standardized by 3GPP to provide confidentiality and integrity, respectively. It was claimed that f 8 and f 9 are secure if the underlying block cipher is a PseudoRandom Permutation (PRP), where f 9 is a slightly modified version of f 9. In this paper, however, we disprove both claims by showing a counterexample. We first construct a PRP F with the following property: There is a non-zero constant Cst such that for any key K, FK()=(). We then show that f 8 and f 9 are completely insecure if F is used as the underlying block cipher. Therefore, PRP assumption does not necessarily imply the security of f 8 and f 9, and it is impossible to prove their security under PRP assumption. It should be stressed that these results do not imply the original f 8 and f 9 (with KASUMI as the underlying block cipher) are insecure, or broken. They simply undermine their provable security.

In this paper, we propose TMAC. TMAC is a refinement of XCBC such that it requires only two keys while XCBC requires three keys. More precisely, TMAC requires only (k + n)-bit keys while XCBC requires (k + 2n)-bit keys, where k is the key length of the underlying block cipher E and n is its block length. We achieve this by using a universal hash function and the cost is almost negligible. Similar to XCBC, the domain is {0,1}* and it requires no extra invocation of E even if the size of the message is a multiple of n.

In this paper, we study variants of the parallel hash function construction of Damgård. We first show an improvement such that the number of processors is almost a half if |M|=(2s + 1)n for some s, where M is the message to be hashed. We next show that there exists a variant of our parallel hash construction such that it is secure even if the underlying compression function is not necessarily collision-free nor one-way. The cost is that some constant times more processors are required.

It is known that a super-pseudorandom permutation on 2n bits can be obtained from a random function f on n bits and two bi-symmetric and AXU hash functions h1 and h2 on n bits. It has a Feistel type structure which is usually denoted by φ(h1,f, f, h2). Bi-symmetric and AXU hash functions h1,h2 are much weaker primitives than a random function f and they can be computed much faster than random functions. This paper shows that we can further weaken the condition on h1.